//////////////////////////////////////////////////////////////////////////
//
//		FileName	-	kdTree3D.h
//		Programmer	-	Sujal Bista
//
//		templatized 3D spatial structure
//
///////////////////////////////////////////////////////////////////////////
#ifndef _KD_TREE_3D_H
#define _KD_TREE_3D_H

#include "global.h"

namespace kdTreeData3D
{
	//struct of the node data
	class stacklessNodeData
	{
		public:
			floatBox boundary;		//boundary of the node
			int index;		//index of data can be a node or data itself
			unsigned int count; //count of the data
			bool isLeaf;

			//prints to the output stream
			friend std::ostream& operator<<(std::ostream &out, const stacklessNodeData& data)
			{
				out<<data.boundary<<"\t index: "<<data.index<<"\t count: "<<data.count<<"\t isLeaf: "<<data.isLeaf;
				return out;
			}
	};

	//struct of the node data
	//used while processing
	class levelNodeData
	{
		public:
			floatBox boundary;		//boundary of the node
			int index;		//index of data can be a node or data
			unsigned int count; //count of the data
			bool isLeaf;
			unsigned int dividingAxis; //axis of the median 0=x,1=y,2=z
			float median;	//value of the media
			unsigned int childIndex; //variable used to save starting indices of the childrens

			//levelNodeData(void)
			//{
			//	count=0;
			//	index=-1;
			//	isLeaf=true;
			//	childIndex=0;
			//}
			
			//prints to the output stream
			friend std::ostream& operator<<(std::ostream &out, const levelNodeData& data)
			{
				out<<data.boundary<<"\t index: "<<data.index<<"\t count: "<<data.count<<"\t axis "<<data.dividingAxis<<"\t isLeaf: "<<data.isLeaf<<"\tmedian "<<data.median;
				return out;
			}

			//returns boundary of left child
			floatBox getLeftChildBoundary(void)
			{
				//create child boundary
				floatBox leftChildBoundary=boundary;

				if(dividingAxis==0)
					leftChildBoundary.maxX=median;
				else if(dividingAxis==1)
					leftChildBoundary.maxY=median;
				else
					leftChildBoundary.maxZ=median;
				return leftChildBoundary;
			}

			//returns boundary of right child
			floatBox getRightChildBoundary(void)
			{
				//create child boundary
				floatBox rightChildBoundary=boundary;

				if(dividingAxis==0)
					rightChildBoundary.minX=median;
				else if(dividingAxis==1)
					rightChildBoundary.minY=median;
				else				
					rightChildBoundary.minZ=median;
				return rightChildBoundary;
			}			
	};
}

class kdTree3D
{
	private:
		//boundary covered by tree
		floatBox boundary;

		//maximum tree height
		unsigned int maxAllowedHeight;

		//optimum number of data in leaf
		unsigned int optimunDataCount;

		//dimension of the data
		unsigned int dataDimension;

		//total count
		unsigned int count;

		//contains all the nodes of the tree
		kdTreeData3D::stacklessNodeData *treeData;

		//contain all the data of the tree
		floatFace *data;

		//indices to the data
		unsigned int *indices;

		//count of stackless data
		unsigned int treeDataCount;

		//height of the tree
		unsigned int treeHeight;
	
	public:		
		
		//default const
		kdTree3D(void);
		//constructor
		kdTree3D(const float &minX,const float &minY,const float &minZ,const float &maxX,const float &maxY,const float &maxZ,unsigned int maxAllowedHeight,unsigned int optimunDataCount);
		//sets boundary
		void setBoundary(const float &minX,const float &minY,const float &minZ,const float &maxX,const float &maxY,const float &maxZ);
		//add a data
		bool add(floatFace *inData, unsigned int inDataCount);
		//searches for the node
		//need to allocate memory
		bool find(floatFace *keys, unsigned int keysCount,int *&resultIndices);
		//searches for the node
		//need to allocate memory
		bool findNearestK(float3 *keys, unsigned int keysCount,unsigned int k,int *&resultIndices);
		//searches for the node within the given radius
		bool findRadius(float3 *keys, unsigned int keysCount,float radius,int *&resultIndices,unsigned int *&resultsPosition,unsigned int &resultsCount);
		//intersect ray
		//need to allocate memory
		bool intersectRays(floatRayData *rays,unsigned int raysCount,unsigned int k,int *&resultIndices, float *&t);
		//intersect individual ray
		bool intersectRay(floatRayData &ray,int &resultIndex, float &t);
		//prints to the output stream
		std::ostream &print(std::ostream &out);
		//returns total number of nodes in the tree
		int getTotalNodes(unsigned int height);
		//clear the entire tree
		void clear(void);	
		//destructor
		~kdTree3D();
	
	private:

		//find the median
		void findMedianCPU(kdTreeData3D::levelNodeData *tData,unsigned int &dataCount,floatFace *data) const;
		//prints to the output stream
		std::ostream &printHelper(std::ostream &out,kdTreeData3D::stacklessNodeData *treeData,unsigned int nodeIndex,floatFace *data,unsigned int *indices,unsigned int level) const;
		//const floatFace *data						//actual input data
		void splitCPU(kdTreeData3D::levelNodeData *&nodeData, unsigned int &nodesCount, const unsigned int &levelStartIndex, const unsigned int &levelCount,const unsigned int &childStartIndex,unsigned int &childLevelCount,unsigned int *&childIndices,unsigned int &childIndexCount,unsigned int &freeChildIndicesIndex,unsigned int &occupiedChildIndicesIndex,const floatFace *data);
		//searches for the nodes in cpu
		int *findHelperCPU(floatFace *keys, unsigned int keysCount);
		//searches for the nodes in cpu
		int *findNearestKHelperCPU(float3 *keys, unsigned int keysCount, unsigned int k);
		//searches for nodes within a ridius
		void findRadiusHelperCPU(float3 *keys, unsigned int keysCount, float radius, int *&indices, unsigned int *&prefixSumResultsCount,unsigned int &totalResultsCount);
		//intersect ray cpu helper
		void intersectRayHelperCPU(floatRayData &currRay,unsigned int k,int *indices, float *t,int *farChildrenIndices,int *tempIndices,float *distance);
};



#endif